package MyString;

import java.util.Stack;

/**
 * 394. 字符串解码
 *
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 */

/**
 * 这题抓住精髓 括号左边 一直有一个字符串和一个数字;默认为空和0；
 * 每次左括号的时候，字符串 res(tmp) 和数字 num 分别进栈
 * 直到出现右括号，当前的字符串变为 tmp + res * num
 * 最后的结果就是 res
 */
public class Leetcode0394_noo {
    public static String decodeString(String s) {
        Stack<Integer> si = new Stack<>();
        Stack<String> sc = new Stack<>();
        int num = 0;
        String res = "";
        for(int i=0; i<s.length(); i++){
            if(Character.isDigit(s.charAt(i))){
                num = num * 10 + s.charAt(i) - '0';
            }else if(s.charAt(i) == '['){
                sc.push(res);
                si.push(num);
                System.out.println("push " + res + " " +num);
                res = "";
                num = 0;
            }else if(s.charAt(i) == ']'){
                int repeat = si.peek();
                si.pop();
                String tmp = sc.peek();
                sc.pop();
                for(int rr=0; rr<repeat; rr++){
                    tmp += res;
                }
                res = tmp;
            }else{
                res += s.charAt(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String ss = "3[a2[c]]";
        System.out.println(decodeString(ss));
    }
}
